/*
给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：

你是否可以使用 O(1) 空间解决此题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

时间复杂度：O(N)，其中 N 为链表中节点的数目。在最初判断快慢指针是否相遇时，slow 指针走过的距离不会超过链表的总长度；随后寻找入环点时，走过的距离也不会超过链表的总长度。因此，总的执行时间为 O(N)+O(N)=O(N)。

空间复杂度：O(1)。我们只使用了 slow,fast

* */
var detectCycle = function(head) {
  if (head === null) return head;
  let slow = head;
  let fast = head;
  let isCycle = false;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast){
      isCycle = true;
      break;
    }
  }
  if (!isCycle) {
    return null;
  }

  //就是在lc141的基础上 再根据 “当两个指针在环内相逢后, 将任意一指针重新指向开头, 当它们再次相逢时, 就是入环口节点所在之处” 这个定理来找到入口

  fast = head; //相遇后 将任意一指针放在开头
  while (slow !== fast) { // 当它们再次相等时 则是入环口节点所在之处
    slow = slow.next;
    fast = fast.next;
  }
  return slow;
};
